package com.since.algorithm.sort;

import java.util.Arrays;

/**
 * Created by Sincerity on 2020/5/14.
 * 描述：描述：八大排序
 * 选择排序
 * 1.分步图解选择排序{@link #stepAnalysisSelectSort(int[])}
 * 2.选择排序算法实现{@link #selectSort(int[])}
 */
class SelectSort {

    public static void main(String[] args) {
        int[] array = {156, 495, 2, 16, -45, 982, 23};
//        stepAnalysisSelectSort(array);
        selectSort(array);
    }

    /**
     * 选择排序
     *
     * @param array 目标数组
     */
    public static void selectSort(int[] array) {
        for (int i = 0; i < array.length - 1; i++) {
            int minIndex = i;
            int min = array[i];
            //让i+1的位置和i进行对比
            for (int j = i + 1; j < array.length; j++) {
                min = array[minIndex];
                if (min > array[j]) {
                    //把最小值放到i位置
                    min = array[j];
                    //记录最小值的索引
                    minIndex = j;
                }
            }
            // 将最小值，放在arr[0], 即交换array[minIndex]<=>min
            if (minIndex != i) {
                array[minIndex] = array[i];
                array[i] = min;
            }
            System.out.println("第" + (i + 1) + "次排序后的数组:" + Arrays.toString(array));
        }
    }

    /**
     * 分步骤去解决选择算法
     *
     * @param array 目标数组
     */
    private static void stepAnalysisSelectSort(int[] array) {
        //分步来实现选择排序
        //第一步:将0位置的数字和剩下的位置数字相比较 最小的放到0位置
        int temp;
        for (int i = 1; i < array.length; i++) {
            temp = array[0];
            if (temp > array[i]) {
                array[0] = array[i];
                array[i] = temp;
            }
        }
        System.out.println("第一次排序后的数组:" + Arrays.toString(array));
        //第二步:将1位置的数字和剩下的2位置数字相比较 最小的放到1位置
        for (int i = 2; i < array.length; i++) {
            temp = array[1];
            if (temp > array[i]) {
                array[1] = array[i];
                array[i] = temp;
            }
        }
        System.out.println("第二次排序后的数组:" + Arrays.toString(array));
        //第二步:将1位置的数字和剩下的2位置数字相比较 最小的放到1位置
        for (int i = 3; i < array.length; i++) {
            temp = array[2];
            if (temp > array[i]) {
                array[2] = array[i];
                array[i] = temp;
            }
        }
        System.out.println("第三次排序后的数组:" + Arrays.toString(array));
    }

}
